作者:rui_er,转载请注明出处。
0 由于 latex 炸了,建议前往洛谷博客查看 Link
本博客为了方便自己查阅,同时也方便大家了解,但因为我嘤语很菜,所以难免有翻译错的地方,还请评论区纠正。
未注明资料来源的均为常识积累。
1 CodeForces rating 规则
1.1 CodeForces rating 与名字颜色换算
设 r 表示 rating,则 CodeForces 的名字颜色有以下几等:(从低到高)
- 黑色不加粗(代码
#000000):Unrated,没有参加过比赛。
- 黑色(代码
#000000):Headquarters,管理员。
- 灰色(代码
#808080):Newbie,r<1200。
- 绿色(代码
#008000):Pupil,1200≤r<1400。
- 青色(代码
#03a89e):Specialist,1400<r≤1600。
- 蓝色(代码
#0000ff):Expert,1600<r≤1900。
- 紫色(代码
#aa00aa):Candidate Master,1900≤r<2100。
- 橙色(代码
#ff8c00):Master,2100≤r<2300。
- 橙色(代码
#ff8c00):International Master,2300≤r<2400。
- 红色(代码
#ff0000):Grandmaster,2400≤r<2600。
- 红色(代码
#ff0000):International Grandmaster,2600≤r<3000。
- 首字母黑色+红色(代码
#ff0000(:first-letter 伪类为 #000000)):Legendary Grandmaster,r≥3000。
1.2 CodeForces rating 与是否计入比赛(及比赛赛制)
除非赛时因为 CodeForces 爆炸等原因 Unrated,否则比赛 rated 的范围如下:
- Div.4:r<1400,exICPC 赛制。
- Div.3:r<1600,exICPC 赛制。
- Div.2 Only:r<2100,CF 赛制。
- Div.2:r<1900,CF 赛制。
- Div.1:r≥1900,CF 赛制。
- Educational Round:r<2100,exICPC 赛制。
- Global Round:Rated for all,CF 赛制。
- 其他比赛:见赛前通知。
1.3 CodeForces rating 在 rated 比赛中的计算
此部分资料来源:翻译自 Open Codeforces Rating System [updated on October 2015]。
假设每一个人原来的 rating 为 ri,则根据以下公式计算 i 在比赛中得分高于 j 的概率:
Pi,j=1+10400rj−ri1
因此我们可以由两人的 rating 差值算出他们其中一个比另一个得分高的期望概率。例如,如果两个人的 rating 差为 200,则 rating 高的人赢过另一方的概率被认为是 0.75;若 rating 差为 400,则这一概率约为 0.9。
根据这一概率,我们可以得到每个选手赛后的期望排名:
seedi=j=ij=1∑nPj,i+1
例如,在 Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) 以前,tourist 的 rating 为 3503,因此期望排名约为 1.7;Petr 的 rating 为 3029,因此期望排名约为 10.7。
一般的想法就是,如果实际排名比 seedi 更靠前,增加 rating;反之减少。
这里计算出 seedi 与实际排名的几何平均数:
mi=seedi×ranki
则我们二分查找出一个 Ri 使得该用户计算出的 seedi=mi。显然 ri 应该像更靠近 Ri 的方向变化。我们取 di=2Ri−ri 作为该用户的 rating 变化值。
不过我们为了让 rating 的平均变化更接近 0,还需进行以下微调:
定义一个数 inc,让所有 di 增加 inc。
第一次微调:
inc=n−1−∑di
保证所有人的平均变化接近 0 但在 0 以下。
第二次微调:
取前 s=min(n,4n) 高的人,取一个合理地 inc 使得前 s 人的平均变化为 0。但是 inc 也不能太大,因此去 inc=min(max(inc,−10),0),用这个值进行第二次微调。
CodeForces rating 计算的源码地址:Link。
1.4 CodeForces rating 初始值
此部分资料来源:Codeforces: Soon We Will Change the Rating Calculation for New Accounts。
以前的初始值都是 1500 分,但在 2020.6 前后,CodeForces 更改了 rating 规则。
新注册的号(或未打过比赛的号)的初始 rating 是 0 而不是 1500。
对于比较新的号 rating 也会有不同的计算方式:
在第一场比赛中,将 rating 看作 1400 来计算变化,然后计算后的 rating 会变成 500+d1。
在第二场比赛中,将 rating 看作 1400+d1 来计算变化,然后计算后的 rating 会变成 500+d1+350+d2。
前六场比赛都是类似的方法,每次加的数是 500,350,250,150,100,50,总和为 1400。
以后的场按正常方式计算。
2 AtCoder 规则
2.1 AtCoder rating 与名字颜色换算
鉴于自己只打过 3 场 AtCoder,此部分待补充。
2.2 AtCoder 可参加比赛的 rating
ABC、ARC、AGC 比赛界面可以查看。
一般地:
- ABC:0≤r<2000。
- ARC:0≤r<2800。
- AGC:Rated for all。
2.3 AtCoder rating 在 rated 比赛中的计算
此部分资料来源:翻译自 AtCoder Rating System ver. 1.00。
在每场比赛后,你都有一个 performance 值 X。如果算出的这个值稳定在 X,则你的 rating 会从 X−1200 逐渐上升为 X。不用担心在第一场比赛中得到很低的 rating,你的真实水平可以在大于 10 场比赛后大致看出。
你可以在 https://atcoder.jp/users/{username}/history 查看你每场比赛的 performance 被四舍五入后的值,下面是计算方法:
对于每个参赛者,我们求出平均 perf:(这里 Perf1∼Perfk 表示各场比赛获得的 perf,不四舍五入,时间从后向前)
APerf=∑i=1k0.9i∑i=1kPerfi×0.9i
对于没打过比赛的萌新来讲怎么办?我们设置 Center 作为 APerf:
Center=⎩⎪⎨⎪⎧800,1000,1200,ABCARCAGC
令 n 为参赛人数,APerfi 表示 i 的 APerf 值,则排名为 r 的人的 perf 记为 X,为下面方程的解:
i=1∑n1+6.0400.0X−APerfi1=r−0.5
对于并列的人,r 取他们 rank 的平均值。
对于第一场比赛,进行特判:
Perf=(Perf−Center)×1.5+Center
最后,真实的 perf 计算如下:
RPerf=min(Perf,RATEDBOUND+400)
其中 RATEDBOUND 表示 rated 的最大范围,见上一条。
计算完了 perf,让我们一起计算一下 rating!
什么你跟我说前面算了这么多乱七八糟的都没算 rating?
是的就是这个意思。
定义以下函数:
F(n)=∑i=1n0.9i∑i=1n0.81i
f(n)=F(1)−F(∞)F(n)−F(∞)×1200
g(x)=2800x
则:
Rating=g−1(∑i=1k0.9i∑i=1kg(RPerfi−f(i))×0.9i)
注意到 g 是一个指数函数,大概是说当你被降智时做出 1 题和做出 4 题差异不大,但是超常发挥时做出 5 题和 6 题的差异要大得多。
换句话说就是超常发挥是让你高兴很久,发挥失常时只用伤心一会(???